// 题目描述
// 在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
// 不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。 
// 给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。

// 输入描述
// 第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。
// 接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。

// 输出描述
// 输出联通所有岛屿的最小路径总距离

// 输入示例
// 7 11
// 1 2 1
// 1 3 1
// 1 5 2
// 2 6 1
// 2 4 2
// 2 3 2
// 3 4 1
// 4 5 1
// 5 6 2
// 5 7 1
// 6 7 1

// 输出示例
// 6

// 提示信息
// 数据范围：
// 2 <= V <= 10000;
// 1 <= E <= 100000;
// 0 <= val <= 10000;


const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// prim算法
void async function () {
    line = await readline()
    let [m, n] = line.split(' ').map((i) => parseInt(i)),
        // 初始化邻接矩阵
        graph = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(10001)),
        // 初始化最小边权值（未生成树距离生成树的最近距离）
        minDist = new Array(m + 1).fill(10001),
        // 初始化已遍历的生成树
        isInTree = new Array(m + 1).fill(false),
        // 初始化到该节点的最小边权值的节点
        path = new Array(m + 1).fill(1);
    while (line = await readline()) {
        // 初始化邻接矩阵
        let [a, b, c] = line.split(' ').map((i) => parseInt(i));
        graph[a][b] = c
        graph[b][a] = c
    }

    // 只需要循环m-1个节点，最后一个节点可以不用遍历（7个节点只需要六条边）
    for (let i = 1; i < m; i++) {
        // prim算法第一步，找到当前要遍历的节点，距离生成树最近的节点（边权值最小）
        let minLength = Infinity,
            cur = null;
        for (let j = 1; j <= m; j++) {
            if (isInTree[j] === false && minDist[j] < minLength) {
                minLength = minDist[j]
                // 第一个值是1，因为后面的minDist的值都相等，不会再进来
                // 后续会进来非生成树中最小的那条边
                cur = j
            }
        }
        console.log(cur,minDist)   // 输出见下方


        // prim算法第二步，将离生成树最近的节点加入生成树中
        isInTree[cur] = true

        // prim算法第三步，更新新加入的节点相邻的边权值，未在生成树中的且较小的进行更新
        for (let j = 1; j <= m; j++) {
            if (isInTree[j] === false && minDist[j] > graph[cur][j]) {
                minDist[j] = graph[cur][j]
                path[j] = cur  // 添加边
            }
        }
    }

    console.log(minDist.slice(2).reduce((sum, cur) => sum + cur, 0))
    console.log(path)  // [1, 1, 1, 1, 3, 4, 2, 5]

}()


1 [
    10001, 10001,
    10001, 10001,
    10001, 10001,
    10001, 10001
  ]
  2 [
    10001, 10001, 1,
        1, 10001, 2,
    10001, 10001
  ]
  3 [
    10001, 10001, 1,
        1,     2, 2,
        1, 10001
  ]
  4 [
    10001, 10001, 1,
        1,     1, 2,
        1, 10001
  ]
  5 [
    10001, 10001, 1,
        1,     1, 1,
        1, 10001
  ]
  6 [
    10001, 10001, 1,
        1,     1, 1,
        1,     1
  ]